package com.fmm.hard;

public class CouplesSwaps {

    /**
     * @param row 情侣的座位情况，每个值表示情侣的号码
     * @return 要让所有情侣都挨着坐，最少交换多少次
     * */
    public static int minSwapsCouples(int[] row) {
        // 记录交换次数
        int result = 0;
        // 遍历座位，只遍历偶数位置，从当前位置后面一位开始找，找到匹配的情侣的位置，和他交换
        for (int i = 0; i < row.length; i += 2) {
            int c1 = row[i];
            int partner;
            // 如果当前的人是偶数，他的情侣一定是比他大 1
            if (c1 % 2 == 0) {
                partner = c1 + 1;
            } else {
                // 如果当前是奇数，他的情侣一定比他小 1
                partner = c1 - 1;
            }
            // 从当前位置后面一位开始查找情侣
            int partnerIndex = findPartnerIndex(row, partner, i + 1);
            // 如果找到的位置不是当前位置的下面一位，则需要交换，如果正好是下面一位，则不需要交换
            if (partnerIndex != i+1) {
                // 交换找到的情侣位置
                int temp = row[i + 1];
                row[i + 1] = row[partnerIndex];
                row[partnerIndex] = temp;
                result++;
            }
        }
        return result;
    }

    private static int findPartnerIndex(int[] row, int partner, int fromIndex) {
        for (int i = fromIndex; i < row.length; i++) {
            if (row[i] == partner) {
                return i;
            }
        }
        return -1;
    }
}
